package cn.gs.algorithm.graph;

import java.util.*;
import java.util.Map.Entry;

/**
 *
 * @author gs
 */
public class Graph<T> {

    Map<T, LinkSet<T>> links = new HashMap<T, LinkSet<T>>();

    public Set<T> nodes() {
        return links.keySet();
    }

    public Set<T> outers(T node) {
        return Collections.unmodifiableSet(addNode(node).outer);
    }

    public Set<T> inners(T node) {
        return Collections.unmodifiableSet(addNode(node).inner);
    }

    /**
     *
     * @return <null> if cannot topSort.
     */
    public List<T> topSort() {
        T root = null;
        addNode(root);
        for (T t : links.keySet()) {
            if (t != root && links.get(t).getInner().isEmpty()) {
                addOutLink(root, t);
            }
        }
        List<T> result = new LinkedList<T>();
        Set<T> visited = new HashSet<T>();
        boolean b = topSortDfs(root, result, visited);
        if (!b) {
            return null;
        }
        if (visited.size() != result.size()) {
            return null;
        }
        delNode(root);
        result.remove(root);
        Collections.reverse(result);
        return result;
    }

    private boolean topSortDfs(T node, List<T> result, Set<T> visited) {
        if (visited.add(node)) {
            LinkSet<T> set = links.get(node);
            if (set != null) {
                for (T n : set.getOuter()) {
                    boolean b = topSortDfs(n, result, visited);
                    if (!b) {
                        return false;
                    }
                }
            }
            result.add(node);
            return true;
        } else {
            return result.contains(node);
        }
    }

    //only suit for undirected-graph
    public Set<Graph> forests() {
        Set<T> nodes = links.keySet();
        Set<Graph> roots = new HashSet<Graph>();
        while (!nodes.isEmpty()) {
            T root = nodes.iterator().next();
            List<T> ds = dfs(root);
            nodes.removeAll(ds);
            Graph g = new Graph();
            for (T d : ds) {
                g.links.put(d, links.get(d));
            }
        }
        return roots;
    }

    public int forestCount() {
        return forests().size();
    }

    public List<T> dfs(T key) {
        List<T> result = new LinkedList<T>();
        dfs(key, result, new HashSet<T>());
        return result;
    }

    private void dfs(T node, List<T> result, Set<T> visited) {
        if (visited.add(node)) {
            LinkSet<T> set = links.get(node);
            if (set != null) {
                result.add(node);
                for (T n : set.getOuter()) {
                    dfs(n, result, visited);
                }
            }
        }
    }

    public int nodeCount() {
        return links.size();
    }

    public int linkCount() {
        int c = 0;
        for (Entry<T, LinkSet<T>> e : links.entrySet()) {
            c += e.getValue().linkCount();
        }
        return c / 2;
    }

    public int biLinkCount() {
        int c = 0;
        for (Entry<T, LinkSet<T>> e : links.entrySet()) {
            c += e.getValue().biLinkCount();
        }
        return c / 2;
    }

    public void clear() {
        links.clear();
    }

    public boolean delBiLinks(Collection<T> x, Collection<T> y) {
        boolean b = true;
        b &= delOutLinks(x, y);
        b &= delInLinks(x, y);
        return b;
    }

    public boolean delOutLinks(Collection<T> x, Collection<T> y) {
        boolean b = true;
        for (T p : x) {
            for (T q : y) {
                b &= delOutLink(p, q);
            }
        }
        return b;
    }

    public boolean delInLinks(Collection<T> x, Collection<T> y) {
        return delOutLinks(y, x);
    }

    public boolean delBiLink(T p, T q) {
        boolean b = true;
        b &= delOutLink(p, q);
        b &= delInLink(p, q);
        return b;
    }

    public boolean delOutLink(T p, T q) {
        boolean flag = true;
        LinkSet<T> x = links.get(p);
        if (x != null) {
            flag &= x.delOutLink(q);
        }
        LinkSet<T> y = links.get(q);
        if (y != null) {
            flag &= y.delInLink(p);
        }
        return flag;
    }

    public boolean delInLink(T p, T q) {
        return delOutLink(q, p);
    }

    public boolean delNode(T key) {
        LinkSet<T> set = links.remove(key);
        if (set != null) {
            delOutLinks(Arrays.asList(key), set.getOuter());
            delInLinks(Arrays.asList(key), set.getInner());
            return true;
        } else {
            return false;
        }
    }

    public boolean addBiLinks(Collection<T> x, Collection<T> y) {
        boolean b = true;
        b &= addOutLinks(x, y);
        b &= addInLinks(x, y);
        return b;
    }

    public boolean addOutLinks(Collection<T> x, Collection<T> y) {
        boolean b = true;
        for (T p : x) {
            LinkSet<T> set = links.get(p);
            if (set != null) {
                b &= set.addOutLinks(y);
            } else {
                b = false;
            }
        }
        return b;
    }

    public boolean addInLinks(Collection<T> x, Collection<T> y) {
        return addOutLinks(y, x);
    }

    public boolean addBiLink(T p, T q) {
        boolean b = true;
        b &= addOutLink(p, q);
        b &= addInLink(p, q);
        return b;
    }

    public boolean addOutLink(T p, T q) {
        LinkSet<T> x = addNode(p);
        LinkSet<T> y = addNode(q);
        return x.addOutLink(q) & y.addInLink(p);
    }

    public boolean addInLink(T p, T q) {
        return addOutLink(q, p);
    }

    public LinkSet<T> addNode(T key) {
        LinkSet<T> set = links.get(key);
        if (set == null) {
            set = new LinkSet<T>();
            links.put(key, set);
        }
        return set;
    }

    public Map<T, LinkSet<T>> getLinks() {
        return links;
    }

    public void setLinks(Map<T, LinkSet<T>> links) {
        this.links = links;
    }

    public static class LinkSet<T> {

        //out -> inn
        Set<T> outer = new HashSet<T>();
        Set<T> inner = new HashSet<T>();

        public int linkCount() {
            return outer.size() + inner.size();
        }

        public int biLinkCount() {
            Set<T> zz = new HashSet<T>();
            zz.addAll(outer);
            zz.removeAll(inner);
            return linkCount() - zz.size();
        }

        public Set<T> biLinks() {
            Set<T> zz = new HashSet<T>();
            zz.addAll(outer);
            zz.removeAll(inner);
            Set<T> yy = new HashSet<T>();
            yy.addAll(outer);
            yy.removeAll(zz);
            return yy;
        }

        boolean delBiLinks(Collection<T> t) {
            boolean b = true;
            b &= delOutLinks(t);
            b &= delInLinks(t);
            return b;
        }

        boolean delOutLinks(Collection<T> t) {
            return outer.removeAll(t);
        }

        boolean delInLinks(Collection<T> t) {
            return inner.removeAll(t);
        }

        boolean delBiLink(T node) {
            boolean b = true;
            b &= delOutLink(node);
            b &= delInLink(node);
            return b;
        }

        boolean delOutLink(T node) {
            return outer.remove(node);
        }

        boolean delInLink(T node) {
            return inner.remove(node);
        }

        private boolean addBiLinks(Collection<T> t) {
            boolean b = true;
            b &= addOutLinks(t);
            b &= addInLinks(t);
            return b;
        }

        boolean addOutLinks(Collection<T> t) {
            return outer.addAll(t);
        }

        private boolean addInLinks(Collection<T> t) {
            return inner.addAll(t);
        }

        boolean addBiLink(T node) {
            boolean b = true;
            b &= addOutLink(node);
            b &= addInLink(node);
            return b;
        }

        boolean addOutLink(T node) {
            return outer.add(node);
        }

        boolean addInLink(T node) {
            return inner.add(node);
        }

        public Set<T> getOuter() {
            return outer;
        }

        public void setOuter(Set<T> outer) {
            this.outer = outer;
        }

        public Set<T> getInner() {
            return inner;
        }

        public void setInner(Set<T> inner) {
            this.inner = inner;
        }
    }
}
